package com.note.feng.leetcode.algorithms.easy.twelve;

public class ThousandTwoHuandredEightySeven {

    /**
     * 1287 有序数组中出现次数超过25%的元素
     * 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
     *
     * 请你找到并返回这个整数
     *
     * 示例：
     *
     * 输入：arr = [1,2,2,6,6,6,6,7,10]
     * 输出：6
     *
     * 提示：
     *
     * 1 <= arr.length <= 10^4
     * 0 <= arr[i] <= 10^5
     */
    /**
     * 解法：双指针
     * 数组为有序数组，相同的数字一定是连续的，
     * 遍历数组，若当前下标元素和距离0.25长度的下标元素相同，直接返回，
     * 否则返回数组最后一个元素或者后面数0.25处元素
     * @param arr
     * @return
     */
    public int findSpecialInteger(int[] arr) {
        int length = arr.length, len = length / 4;
        for(int i = 0; i < length - len; i ++){
            if(arr[i] == arr[i + len]){
                return arr[i];
            }
        }
        return arr[length - len];
    }
}
